/*
 * @lc app=leetcode id=124 lang=cpp
 *
 * [124] Binary Tree Maximum Path Sum
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        if (!root) {
            return 0;
        }

        int maxSum = INT_MIN;
        maxPathSum(root, maxSum);
        return maxSum;
    }

    int maxPathSum(TreeNode* node, int& maxSum) {
        if (!node) {
            return 0;
        }

        int val = node->val;
        if (!node->left && !node->right) {
            if (val > maxSum) {
                maxSum = val;
            }
            return val;
        }

        int valLeft = maxPathSum(node->left, maxSum);
        int valright = maxPathSum(node->right, maxSum);
        int maxChild = std::max(0, std::max(valLeft, valright));

        int rootSum = val;
        if (valLeft > 0) {
            rootSum += valLeft;
        }

        if (valright > 0) {
            rootSum += valright;
        }

        if (rootSum > maxSum) {
            maxSum = rootSum;
        }

        return val + maxChild;
    }

};

